By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 26, Issue 3, pp. 605-872

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Boolean Circuits, Tensor Ranks, and Communication Complexity

Pavel Pudlák, Vojtech Rödl, and Jirí Sgall

pp. 605-633

BibTeX  Abstract Full Text:  PDF

Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete Sets

Lane A. Hemaspaandra and Jörg Rothe

pp. 634-653

BibTeX  Abstract Full Text:  PDF

Ray Shooting Amidst Spheres in Three Dimensions and Related Problems

Shai Mohaban and Micha Sharir

pp. 654-674

BibTeX  Abstract Full Text:  PDF

On the Complexity of Finding a Minimum Cycle Cover of a Graph

Carsten Thomassen

pp. 675-677

BibTeX  Abstract Full Text:  PDF

An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs

Akiyoshi Shioura, Akihisa Tamura, and Takeaki Uno

pp. 678-692

BibTeX  Abstract Full Text:  PDF

Size--Depth Tradeoffs for Threshold Circuits

Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks

pp. 693-707

BibTeX  Abstract Full Text:  PDF

Bounds for the Computational Power and Learning Complexity of Analog Neural Nets

Wolfgang Maass

pp. 708-732

BibTeX  Abstract Full Text:  PDF

On the Amount of Nondeterminism and the Power of Verifying

Liming Cai and Jianer Chen

pp. 733-750

BibTeX  Abstract Full Text:  PDF

Bounds on the Number of Examples Needed for Learning Functions

Hans Ulrich Simon

pp. 751-763

BibTeX  Abstract Full Text:  PDF

A Pumping Condition for Regular Sets

Stefano Varricchio

pp. 764-771

BibTeX  Abstract Full Text:  PDF

Leader Election in Complete Networks

Gurdip Singh

pp. 772-785

BibTeX  Abstract Full Text:  PDF

The Cost of Derandomization: Computability or Competitiveness

Xiaotie Deng and Sanjeev Mahajan

pp. 786-802

BibTeX  Abstract Full Text:  PDF

Tighter Upper Bounds on the Exact Complexity of String Matching

Richard Cole and Ramesh Hariharan

pp. 803-856

BibTeX  Abstract Full Text:  PDF

Thek-Steiner Ratio in Graphs

Al Borchers and Ding-Zhu Du

pp. 857-869

BibTeX  Abstract Full Text:  PDF

A Note on "An On-Line Scheduling Heuristic with Better Worst Case Ratio than Graham's List Scheduling"

R. Chandrasekaran, Bo Chen, Gábor Galambos, P. R. Narayanan, André Van Vliet, and Gerhard J. Woeginger

pp. 870-872

BibTeX  Abstract Full Text:  PDF